package ljl.alg.jianzhioffer.round2;

import commons.TreeNode;

import java.util.LinkedList;

public class _55_1_depth_of_bitree {
    
    public int maxDepth1(TreeNode root) {
        if (root == null) return 0;
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return Math.max(left,right) + 1;
    }
    
    /**
     * 操她妹妹！
     * 写错了！
     * 我第一次是一遍遍历 q 一遍往里插入元素，这么搞是不行的
     * 如果你用普通 for 循环可以
     * */
    // 还有个解法是层序遍历次数
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        int res = 0;
        LinkedList<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            res++;
            
            /*
            // 下面这段也是可以的，不需要不停地 new list 了
            // 这是我掌握的层序遍历，这个增强 for 循环的反而有些奇怪
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = q.poll();
                if (node.left != null) q.offer(node.left);
                if (node.right != null) q.offer(node.right);
            }
            * */
            
            LinkedList<TreeNode> tmp = new LinkedList<>();
            for (TreeNode node : q) {
                if (node.left != null) tmp.offer(node.left);
                if (node.right != null) tmp.offer(node.right);
            }
            q = tmp;
        }
        return res;
    }
}
